// linked_hash_map.h
// C++11 实现版本 (高性能)
#ifndef LINKED_HASH_MAP_H
#define LINKED_HASH_MAP_H

#include <unordered_map>
#include <list>
#include <mutex>
#include <utility>
#include <stdexcept>

template <typename K, typename V, typename Hash = std::hash<K>, typename KeyEqual = std::equal_to<K>>

class LinkedHashMap {
public:
    typedef K key_type;
    typedef V mapped_type;
    typedef std::pair<const K, V> value_type;
    typedef typename std::list<value_type>::iterator list_iterator;
    typedef typename std::list<value_type>::const_iterator const_list_iterator;

    // 自定义迭代器（只读，顺序遍历）
    class const_iterator {
        friend class LinkedHashMap;
    public:
        typedef std::bidirectional_iterator_tag iterator_category;
        typedef value_type value_type;
        typedef std::ptrdiff_t difference_type;
        typedef const value_type* pointer;
        typedef const value_type& reference;

        const_iterator() : list_it_() {}
        const_iterator(const const_list_iterator& it) : list_it_(it) {}

        reference operator*() const { return *list_it_; }
        pointer operator->() const { return &(*list_it_); }

        const_iterator& operator++() { ++list_it_; return *this; }
        const_iterator operator++(int) { const_iterator tmp(*this); ++(*this); return tmp; }
        const_iterator& operator--() { --list_it_; return *this; }
        const_iterator operator--(int) { const_iterator tmp(*this); --(*this); return tmp; }

        bool operator==(const const_iterator& other) const { return list_it_ == other.list_it_; }
        bool operator!=(const const_iterator& other) const { return !(*this == other); }

    private:
        const_list_iterator list_it_;
    };

    // 构造函数
    LinkedHashMap() = default;
    explicit LinkedHashMap(size_t bucket_count, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual())
        : map_(bucket_count, hash, equal) {}

    // 插入或赋值
    void insert(const K& key, const V& value) {
        std::lock_guard<std::mutex> lock(mutex_);
        auto map_it = map_.find(key);
        if (map_it != map_.end()) {
            // 更新值（保持顺序不变）
            map_it->second->second = value;
        } else {
            // 插入新元素到 list 尾部
            list_.push_back(value_type(key, value));
            map_[key] = --list_.end(); // 指向刚插入的元素
        }
    }

    // operator[] 不推荐（难以线程安全），提供 at()
    V& at(const K& key) {
        std::lock_guard<std::mutex> lock(mutex_);
        auto map_it = map_.find(key);
        if (map_it == map_.end()) {
            throw std::out_of_range("key not found");
        }
        return map_it->second->second;
    }

    const V& at(const K& key) const {
        std::lock_guard<std::mutex> lock(mutex_);
        auto map_it = map_.find(key);
        if (map_it == map_.end()) {
            throw std::out_of_range("key not found");
        }
        return map_it->second->second;
    }

    // 查找
    const_iterator find(const K& key) const {
        std::lock_guard<std::mutex> lock(mutex_);
        auto map_it = map_.find(key);
        if (map_it != map_.end()) {
            return const_iterator(map_it->second);
        }
        return end();
    }

    // 删除
    bool erase(const K& key) {
        std::lock_guard<std::mutex> lock(mutex_);
        auto map_it = map_.find(key);
        if (map_it == map_.end()) {
            return false;
        }
        list_.erase(map_it->second);
        map_.erase(map_it);
        return true;
    }

    // 清空
    void clear() {
        std::lock_guard<std::mutex> lock(mutex_);
        map_.clear();
        list_.clear();
    }

    // 获取大小
    size_t size() const {
        std::lock_guard<std::mutex> lock(mutex_);
        return map_.size();
    }

    bool empty() const {
        std::lock_guard<std::mutex> lock(mutex_);
        return map_.empty();
    }

    // 迭代器（顺序）
    const_iterator begin() const {
        std::lock_guard<std::mutex> lock(mutex_);
        return const_iterator(list_.begin());
    }

    const_iterator end() const {
        std::lock_guard<std::mutex> lock(mutex_);
        return const_iterator(list_.end());
    }

private:
    mutable std::mutex mutex_;
    std::unordered_map<K, list_iterator, Hash, KeyEqual> map_; // key -> iterator in list
    std::list<value_type> list_; // 保持插入顺序

    // 禁止拷贝
    LinkedHashMap(const LinkedHashMap&) = delete;
    LinkedHashMap& operator=(const LinkedHashMap&) = delete;
};

#endif // LINKED_HASH_MAP_H